package com.lw.leetcode.arr.b;

import com.lw.leetcode.tree.TreeNode;

/**
 * Created with IntelliJ IDEA.
 * 1026. 节点与其祖先之间的最大差值
 *
 * @author liw
 * @version 1.0
 * @date 2021/12/5 19:13
 */
public class MaxAncestorDiff {


    public static void main(String[] args) {
        MaxAncestorDiff test = new MaxAncestorDiff();
        TreeNode instance = TreeNode.getInstance13();

        int i = test.maxAncestorDiff(instance);
        System.out.println(i);
    }

    private long value = 0;

    public int maxAncestorDiff(TreeNode root) {
        find(root);
        return (int) value;
    }

    private long find(TreeNode node) {
        if (node == null) {
            return -1L;
        }
        long val = node.val;
        long left = find(node.left);
        long right = find(node.right);
        long min = Integer.MAX_VALUE;
        long max = -1L;
        if (left != -1L) {
            long a =left >> 20;
            long b =  left & 0XfffffL;
            min = Math.min(min, b);
            max = Math.max(max, a);
        }
        if (right != -1L) {
            long a = right >> 20;
            long b = right & 0XfffffL;
            min = Math.min(min, b);
            max = Math.max(max, a);
        }
        if (max == -1) {
            return (val << 20) | val;
        }
        value = Math.max(Math.max(Math.abs(val - max), Math.abs(val - min)), value);
        if (val > max) {
            return (val << 20) | min;
        } else if (val < min) {
            return (max << 20) | val;
        }
        return (max << 20) | min;
    }

}
